package 每日一题;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-06
 **/

public class No414第三大的数 {

    /**
     * 给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
     *
     * 示例 1：
     * 输入：[3, 2, 1]
     * 输出：1
     * 解释：第三大的数是 1 。
     * 示例 2：
     * 输入：[1, 2]
     * 输出：2
     * 解释：第三大的数不存在, 所以返回最大的数 2 。
     * 示例 3：
     * 输入：[2, 2, 3, 1]
     * 输出：1
     * 解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
     * 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
     *  
     * 提示：
     * 1 <= nums.length <= 104
     * -231 <= nums[i] <= 231 - 1
     *
     * 进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
     */

    public int thirdMaxGood(int[] nums) {

        Set<Integer> set = new HashSet<>();
        long minNum  = Long.MIN_VALUE;
        long midNum = Long.MIN_VALUE;
        long maxNum = Long.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            if (nums[i] > maxNum) {
                minNum = midNum;
                midNum = maxNum;
                maxNum = nums[i];
            } else if (nums[i] > midNum) {
                minNum = midNum;
                midNum = nums[i];
            } else if (nums[i] > minNum){
                minNum = nums[i];
            }

        }

        if (minNum == Long.MIN_VALUE) {
            return (int) Math.max(midNum, maxNum);
        }

        return (int) minNum;
    }

    // 不够简洁
    public int thirdMax(int[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }

        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }

        Set<Integer> set = new HashSet<>();
        int[] arr = new int[3];

        int a = 0;
        int i = 0;
        for (; i < nums.length && a != 3; i++) {
            if (!set.contains(nums[i])) {
                arr[a++] = nums[i];
                set.add(nums[i]);
            }
        }

        if (a == 1) {
            return arr[0];
        }

        if (a == 2) {
            return Math.max(arr[0], arr[1]);
        }

        Arrays.sort(arr);

        for (i = 3; i < nums.length; i++) {
            sortSwap(arr, nums[i]);
        }

        return arr[0];
    }

    private void sortSwap(int[] arr, int num) {

        if (arr[0] == num || arr[1] == num || arr[2] == num) {
            return;
        }

        if (num > arr[2]) {
            arr[0] = arr[1];
            arr[1] = arr[2];
            arr[2] = num;
            return;
        }

        if (num > arr[1]) {
            arr[0] = arr[1];
            arr[1] = num;
            return;
        }

        if (num > arr[0]) {
            arr[0] = num;
        }

    }

    public static void main(String[] args) {
        No414第三大的数 n = new No414第三大的数();
        int[] arr = {5,2,4,1,3,6,0};
        int result = n.thirdMaxGood(arr);
        System.out.println(result);
    }

}
